/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 25. K 个一组翻转链表
 * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/">...</a>
 * User: DELL
 * Date: 2023-10-22
 * Time: 20:51
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    /**
     * 解题思路:
     * 总体上来说本题每一段均采用头插法进行翻转,同时使用两个标记节点,即 pre 和 next,
     * 分别表示 每一段的前一个节点 和 后一段的第一个节点,借助这两个标记节点进行翻转,
     * 本题就是细品每一个标志位的移动即可.
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 参数校验
        if (head == null || k == 1) {
            return head;
        }
        ListNode newHead = new ListNode(-1, head);   // 新头节点
        ListNode pre = newHead;     // 每一段的前一个节点
        ListNode next = head;       // 后一段的第一个节点
        ListNode cur = null;        // 操作的节点
        while (true) {
            // 先将 next 定位到下一段
            for (int i = 0; i < k; i++) {
                if (next != null) {
                    next = next.next;
                } else {
                    return newHead.next;
                }
            }
            // 定位 cur 到每一组要反转的第二个节点的位置
            cur = pre.next.next;
            // 将 pre.next 置为 next,即将翻转完的下一段和后一段拼接
            pre.next.next = next;
            // 记录以下 pre.next, 方便后续 pre 节点跳转到下一段的 pre 位置
            ListNode temp = pre.next;
            // 使用头插法,共操作 k-1 个节点
            for (int i = 0; i < k - 1; i++) {
                ListNode temp2 = cur.next;
                cur.next = pre.next;
                pre.next = cur;
                cur = temp2;
            }
            pre = temp;
        }
    }
}